package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-31 16:35
 **/
public class LeetCode70 {

    public int climbStairs(int n) {
        if (n < 2) {
            return 1;
        }
        //f[i]表示跳到i级台阶有多少种方式
        //初始条件: f[0] = 1; f[1] = 1; f[2] = 2;
        //转移方程: f[i] = f[i - 1] + f[i - 2] 解释: 跳到i级台阶的方式可以由跳到i-1级台阶和跳到i-2级台阶之和组成
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = (f[i - 1] + f[i - 2]);
        }
        return f[n];
    }

}
